#include<bits/stdc++.h>
using namespace std;
int a[1000005];
int t;

void solve(){
    long long ans = 0;
    memset(a, 0, sizeof(a));
    int n = 0, cur = 0;
    cin >> n;
    for(int i = 1; i <= n; i++){
        cur = 0;
        cin >> cur;
        a[cur]++;
    }
    for(int i = 1; i <= 1000005; i++){
        if(a[i] > 1) ans += i * ((a[i] - a[i] % 2) / 2);
    }
    if(t == n - 1) ans %= 1000005;
    cout << ans << "\n";
}
int main(){
  freopen("color.in", "r", stdin);
  freopen("color.out", "w", stdout);
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}
